package simpledb.index;

import simpledb.common.Database;
import simpledb.common.DbException;
import simpledb.common.Debug;
import simpledb.common.Type;
import simpledb.storage.BufferPool;
import simpledb.storage.Field;
import simpledb.storage.IntField;
import simpledb.storage.RecordId;
import simpledb.execution.Predicate.Op;

import java.io.*;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 每个 BTreeInternalPage 实例用于存储一个 B+ 树文件中的内部节点页（非叶子节点页）的数据，
 * 并实现由 BufferPool 使用的 Page 接口。
 *
 * BTreeInternalPage 是 B+ 树结构中非叶子节点的物理表示，用于管理索引键和子节点指针。
 * 它支持查找、插入、分裂等操作，是构建 B+ 树索引的核心组成部分。
 *
 * @see BTreeFile  - B+ 树文件的整体实现，管理多个内部页和叶子页
 * @see BufferPool - 缓冲池系统，负责管理数据库中页面的加载与缓存
 * @see BTreeLeafPage - 相对应的叶子节点页类
 */
public class BTreeInternalPage extends BTreePage {

    private final byte[]  header;       // 头部信息，标识哪些槽位被使用
    private final Field[] keys;         // 键数组，用于比较和路由
    private final int[]   children;     // 子节点页 ID 数组
    private final int     numSlots;     // 总共的槽位数量（key + child 的数量）
    private int           childCategory; // 子节点类型（leaf 或 internal）

    /**
     * 进行内部一致性检查，确保页的数据结构满足 B+ 树的约束。
     * 包括键的有序性、上下界限制以及节点占用率等。
     *
     * @param lowerBound 当前页的下界（不包含）
     * @param upperBound 当前页的上界（不包含）
     * @param checkOccupancy 是否检查节点的最小占用率
     * @param depth 当前页在树中的深度
     */
    public void checkRep(Field lowerBound, Field upperBound, boolean checkOccupancy, int depth) {
        Field prev = lowerBound;
        assert (this.getId().pgcateg() == BTreePageId.INTERNAL);

        Iterator<BTreeEntry> it = this.iterator();
        while (it.hasNext()) {
            Field f = it.next().getKey();
            assert (null == prev || prev.compare(Op.LESS_THAN_OR_EQ, f));
            prev = f;
        }

        assert null == upperBound || null == prev || (prev.compare(Op.LESS_THAN_OR_EQ, upperBound));

        assert !checkOccupancy || depth <= 0 || (getNumEntries() >= getMaxEntries() / 2);
    }

    /**
     * 从磁盘读取的一组字节数据中创建一个 BTreeInternalPage（B+ 树内部节点页）。
     *
     * 一个 BTreeInternalPage 的格式由以下几部分组成：
     * - 一组“头部字节”（header bytes），用于标识该页中哪些槽位（slot）是被使用的；
     * - 一定数量的“条目槽位”（entry slots），每个条目包含一个键（key）和一个子节点指针（child pointer）；
     * - 额外的一些字节，用于存储父节点指针、额外的一个子节点指针（因为 m 个条目的节点有 m+1 个子节点指针），
     *   以及所有子节点的类型（leaf 或 internal）。
     *
     * 具体来说，该页可以容纳的条目数（entries）等于： <p>
     *     floor((BufferPool.getPageSize()*8 - 额外字节数*8) / (每个条目大小*8 + 1)) <p>
     * 其中每个条目的大小等于键字段大小加上子节点指针所占空间（即 key + child pointer），
     * 可以通过键字段（key）和 Catalog#getTupleDesc 来确定。
     *
     * 头部信息所占的 8 位字（byte）数量等于： <p>
     *     ceiling((entry slots 数量 + 1) / 8) <p>
     *
     * @see Database#getCatalog
     * @see Catalog#getTupleDesc
     * @see BufferPool#getPageSize()
     *
     * @param id - 该页面的唯一标识符（page id）
     * @param data - 页面的原始字节数据（从磁盘读取）
     * @param key - 该索引页所基于的键字段（index key field）
     */
    public BTreeInternalPage(BTreePageId id, byte[] data, int key) throws IOException {
        super(id, key);
        this.numSlots = getMaxEntries() + 1;
        DataInputStream dis = new DataInputStream(new ByteArrayInputStream(data));

        // 读取父指针
        try {
            Field f = Type.INT_TYPE.parse(dis);
            this.parent = ((IntField) f).getValue();
        } catch (java.text.ParseException e) {
            e.printStackTrace();
        }

        // 读取子节点类型（叶子或内部节点）
        childCategory = dis.readByte();

        // 分配并读取页面头部信息
        header = new byte[getHeaderSize()];
        for (int i = 0; i < header.length; i++)
            header[i] = dis.readByte();

        keys = new Field[numSlots];
        try {
            // 分配并读取键值
            keys[0] = null;
            for (int i = 1; i < keys.length; i++)
                keys[i] = readNextKey(dis, i);
        } catch (NoSuchElementException e) {
            e.printStackTrace();
        }

        children = new int[numSlots];
        try {
            // 分配并读取子节点指针
            for (int i = 0; i < children.length; i++)
                children[i] = readNextChild(dis, i);
        } catch (NoSuchElementException e) {
            e.printStackTrace();
        }
        dis.close();

        setBeforeImage(); // 设置“旧数据”快照，用于恢复
    }

    /**
     * 获取此页面最多可以存储的键数量。
     * 计算方式考虑了键大小、额外头信息和指针大小。
     *
     * @return 最大条目数
     */
    public int getMaxEntries() {
        int keySize = td.getFieldType(keyField).getLen();
        int bitsPerEntryIncludingHeader = keySize * 8 + INDEX_SIZE * 8 + 1;
        int extraBits = 2 * INDEX_SIZE * 8 + 8 + 1; // 父指针、子节点类型、额外子指针、额外头比特
        return (BufferPool.getPageSize() * 8 - extraBits) / bitsPerEntryIncludingHeader;
    }

    /**
     * 计算 B+ 树内部页头部所需的字节数。
     *
     * @return 头部所需字节数
     */
    private int getHeaderSize() {
        int slotsPerPage = getMaxEntries() + 1;
        int hb = (slotsPerPage / 8);
        if (hb * 8 < slotsPerPage)
            hb++;

        return hb;
    }

    /**
     * 获取此页面修改前的状态，用于数据库恢复机制。
     *
     * @return 修改前的页面副本
     */
    public BTreeInternalPage getBeforeImage() {
        try {
            byte[] oldDataRef = null;
            synchronized (oldDataLock) {
                oldDataRef = oldData;
            }
            return new BTreeInternalPage(pid, oldDataRef, keyField);
        } catch (IOException e) {
            e.printStackTrace();
            System.exit(1);
        }
        return null;
    }

    /**
     * 设置页面的“旧数据”快照。
     */
    public void setBeforeImage() {
        synchronized (oldDataLock) {
            oldData = getPageData().clone();
        }
    }

    /**
     * 从输入流中读取下一个键值。
     *
     * @param dis 数据输入流
     * @param slotId 槽位编号
     * @return 键字段对象
     */
    private Field readNextKey(DataInputStream dis, int slotId) throws NoSuchElementException {
        if (!isSlotUsed(slotId)) {
            for (int i = 0; i < td.getFieldType(keyField).getLen(); i++) {
                try {
                    dis.readByte();
                } catch (IOException e) {
                    throw new NoSuchElementException("error reading empty key");
                }
            }
            return null;
        }

        Field f = null;
        try {
            f = td.getFieldType(keyField).parse(dis);
        } catch (java.text.ParseException e) {
            e.printStackTrace();
            throw new NoSuchElementException("parsing error!");
        }

        return f;
    }

    /**
     * 从输入流中读取下一个子节点指针。
     *
     * @param dis 数据输入流
     * @param slotId 槽位编号
     * @return 子节点页 ID
     */
    private int readNextChild(DataInputStream dis, int slotId) throws NoSuchElementException {
        if (!isSlotUsed(slotId)) {
            for (int i = 0; i < INDEX_SIZE; i++) {
                try {
                    dis.readByte();
                } catch (IOException e) {
                    throw new NoSuchElementException("error reading empty child pointer");
                }
            }
            return -1;
        }

        int child = -1;
        try {
            Field f = Type.INT_TYPE.parse(dis);
            child = ((IntField) f).getValue();
        } catch (java.text.ParseException e) {
            e.printStackTrace();
            throw new NoSuchElementException("parsing error!");
        }

        return child;
    }

    /**
     * 生成表示此页面内容的字节数组，用于将该页序列化到磁盘。
     * <p>
     * 这个方法的不变式是：可以将 getPageData 生成的 byte[] 传给 BTreeInternalPage 构造函数，
     * 并且能够生成一个完全相同的 BTreeInternalPage 对象。
     *
     * @return 表示当前页面数据的字节数组
     */
    public byte[] getPageData() {
        int len = BufferPool.getPageSize();
        ByteArrayOutputStream baos = new ByteArrayOutputStream(len);
        DataOutputStream dos = new DataOutputStream(baos);

        // 写出父节点指针
        try {
            dos.writeInt(parent);
        } catch (IOException e) {
            e.printStackTrace();
        }

        // 写出子节点类型（叶子或内部节点）
        try {
            dos.writeByte((byte) childCategory);
        } catch (IOException e) {
            e.printStackTrace();
        }

        // 写出头部信息
        for (byte b : header) {
            try {
                dos.writeByte(b);
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        // 写出键值（从索引1开始，因为0号槽位不使用）
        for (int i = 1; i < keys.length; i++) {

            // 空槽位：写入0填充
            if (!isSlotUsed(i)) {
                for (int j = 0; j < td.getFieldType(keyField).getLen(); j++) {
                    try {
                        dos.writeByte(0);
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
                continue;
            }

            // 非空槽位：序列化键字段
            try {
                keys[i].serialize(dos);
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        // 写出子节点指针
        for (int i = 0; i < children.length; i++) {

            // 空槽位：写入0填充
            if (!isSlotUsed(i)) {
                for (int j = 0; j < INDEX_SIZE; j++) {
                    try {
                        dos.writeByte(0);
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
                continue;
            }

            // 非空槽位：写入子节点页ID
            try {
                dos.writeInt(children[i]);
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        // 填充剩余空间为0，保证页面大小固定
        int zerolen = BufferPool.getPageSize()
                      - (INDEX_SIZE + 1 + header.length + td.getFieldType(keyField).getLen() * (keys.length - 1) + INDEX_SIZE
                                                                                                                   * children.length);
        byte[] zeroes = new byte[zerolen];
        try {
            dos.write(zeroes, 0, zerolen);
        } catch (IOException e) {
            e.printStackTrace();
        }

        try {
            dos.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }

        return baos.toByteArray();
    }

    /**
     * 从页面中删除指定的条目（键 + 一个子节点指针）。
     * 使用 RecordId 定位要删除的条目，因此不能为 null。
     * 删除后应将该条目的 RecordId 设为 null，表示不再存储于任何页面。
     *
     * @param e 要删除的条目
     * @param deleteRightChild 如果为 true，则删除右侧子节点；否则删除左侧子节点
     * @throws DbException 如果条目不在本页、或槽位为空
     */
    private void deleteEntry(BTreeEntry e, boolean deleteRightChild) throws DbException {
        RecordId rid = e.getRecordId();
        if (rid == null)
            throw new DbException("尝试删除 recordId 为 null 的条目");

        // 检查是否属于当前页和表
        if ((rid.getPageId().getPageNumber() != pid.getPageNumber())
            || (rid.getPageId().getTableId() != pid.getTableId()))
            throw new DbException("尝试删除无效页或表中的条目");

        // 检查槽位是否被使用
        if (!isSlotUsed(rid.getTupleNumber()))
            throw new DbException("尝试删除空条目");

        // 删除右侧子节点
        if (deleteRightChild) {
            markSlotUsed(rid.getTupleNumber(), false); // 标记为未使用
        } else {
            // 删除左侧子节点时需要调整前一个子节点指针
            for (int i = rid.getTupleNumber() - 1; i >= 0; i--) {
                if (isSlotUsed(i)) {
                    children[i] = children[rid.getTupleNumber()];
                    markSlotUsed(rid.getTupleNumber(), false);
                    break;
                }
            }
        }

        e.setRecordId(null); // 清除记录 ID
    }

    /**
     * 从页面中删除指定的条目（键 + 右侧子节点指针）。
     * 使用 RecordId 定位要删除的条目，因此不能为 null。
     * 删除后应将该条目的 RecordId 设为 null，表示不再存储于任何页面。
     *
     * @param e 要删除的条目
     * @throws DbException 如果条目不在本页、或槽位为空
     */
    public void deleteKeyAndRightChild(BTreeEntry e) throws DbException {
        deleteEntry(e, true);
    }

    /**
     * 从页面中删除指定的条目（键 + 左侧子节点指针）。
     * 使用 RecordId 定位要删除的条目，因此不能为 null。
     * 删除后应将该条目的 RecordId 设为 null，表示不再存储于任何页面。
     *
     * @param e 要删除的条目
     * @throws DbException 如果条目不在本页、或槽位为空
     */
    public void deleteKeyAndLeftChild(BTreeEntry e) throws DbException {
        deleteEntry(e, false);
    }

    /**
     * 根据记录ID（RecordId）更新指定位置条目的键值和/或子节点指针。
     *
     * @param e 要更新的条目（包含新的键值和子节点）
     * @throws DbException 如果该条目不在当前页面、槽位为空、或者更新后的键会破坏顺序
     */
    public void updateEntry(BTreeEntry e) throws DbException {
        RecordId rid = e.getRecordId();
        if (rid == null)
            throw new DbException("尝试更新 recordId 为 null 的条目");
        if ((rid.getPageId().getPageNumber() != pid.getPageNumber())
            || (rid.getPageId().getTableId() != pid.getTableId()))
            throw new DbException("尝试更新无效页或表中的条目");
        if (!isSlotUsed(rid.getTupleNumber()))
            throw new DbException("尝试更新空条目");

        // 检查右侧是否有键小于当前键，保证顺序不变
        for (int i = rid.getTupleNumber() + 1; i < numSlots; i++) {
            if (isSlotUsed(i)) {
                if (keys[i].compare(Op.LESS_THAN, e.getKey())) {
                    throw new DbException("尝试更新条目时键值不合法：" + e.getKey() + " HINT: 更新后的键必须小于等于其右边的键");
                }
                break;
            }
        }

        // 检查左侧是否有键大于当前键，保证顺序不变
        for (int i = rid.getTupleNumber() - 1; i >= 0; i--) {
            if (isSlotUsed(i)) {
                if (i > 0 && keys[i].compare(Op.GREATER_THAN, e.getKey())) {
                    throw new DbException("尝试更新条目时键值不合法：" + e.getKey() + " HINT: 更新后的键必须大于等于其左边的键");
                }
                children[i] = e.getLeftChild().getPageNumber(); // 更新左子节点指针
                break;
            }
        }

        // 更新右子节点指针和键值
        children[rid.getTupleNumber()] = e.getRightChild().getPageNumber();
        keys[rid.getTupleNumber()] = e.getKey();
    }

    /**
     * 将指定条目插入到页面中，并更新其 RecordId 表示它现在存储在本页面。
     *
     * @param e 要插入的条目
     * @throws DbException 如果页面已满、字段类型不匹配、表ID或子节点类型不一致，或条目非法
     */
    public void insertEntry(BTreeEntry e) throws DbException {
        // 键类型检查
        if (!e.getKey().getType().equals(td.getFieldType(keyField)))
            throw new DbException("插入条目时键字段类型不匹配");

        // 左右子节点所属表 ID 必须与当前页相同
        if (e.getLeftChild().getTableId() != pid.getTableId() || e.getRightChild().getTableId() != pid.getTableId())
            throw new DbException("插入条目时表ID不匹配");

        // 子节点类型检查
        if (childCategory == 0) {
            if (e.getLeftChild().pgcateg() != e.getRightChild().pgcateg())
                throw new DbException("插入条目时子节点类型不匹配");
            childCategory = e.getLeftChild().pgcateg();
        } else if (e.getLeftChild().pgcateg() != childCategory || e.getRightChild().pgcateg() != childCategory)
            throw new DbException("插入条目时子节点类型不匹配");

        // 如果这是第一个条目，直接插入
        if (getNumEmptySlots() == getMaxEntries()) {
            children[0] = e.getLeftChild().getPageNumber();
            children[1] = e.getRightChild().getPageNumber();
            keys[1] = e.getKey();
            markSlotUsed(0, true);
            markSlotUsed(1, true);
            e.setRecordId(new RecordId(pid, 1));
            return;
        }

        // 找到一个空槽位插入
        int emptySlot = -1;
        for (int i = 1; i < numSlots; i++) {
            if (!isSlotUsed(i)) {
                emptySlot = i;
                break;
            }
        }
        if (emptySlot == -1)
            throw new DbException("调用 insertEntry 时页面无空槽位");

        // 找到合适的插入位置并校验顺序
        int lessOrEqKey = -1;
        for (int i = 0; i < numSlots; i++) {
            if (isSlotUsed(i)) {
                if (children[i] == e.getLeftChild().getPageNumber() || children[i] == e.getRightChild().getPageNumber()) {
                    if (i > 0 && keys[i].compare(Op.GREATER_THAN, e.getKey())) {
                        throw new DbException("插入非法条目：" + e.toString() + " HINT: 插入键必须介于已有子节点的左右键之间");
                    }
                    lessOrEqKey = i;
                    if (children[i] == e.getRightChild().getPageNumber()) {
                        children[i] = e.getLeftChild().getPageNumber();
                    }
                } else if (lessOrEqKey != -1) {
                    if (keys[i].compare(Op.LESS_THAN, e.getKey())) {
                        throw new DbException("插入非法条目：" + e.toString() + " HINT: 插入键必须介于已有子节点的左右键之间");
                    }
                    break;
                }
            }
        }

        if (lessOrEqKey == -1)
            throw new DbException("插入非法条目：" + e.toString() + " HINT: 插入键必须介于已有子节点的左右键之间");

        // 移动条目以腾出空间，保持顺序
        int goodSlot = -1;
        if (emptySlot < lessOrEqKey) {
            for (int i = emptySlot; i < lessOrEqKey; i++) {
                moveEntry(i + 1, i);
            }
            goodSlot = lessOrEqKey;
        } else {
            for (int i = emptySlot; i > lessOrEqKey + 1; i--) {
                moveEntry(i - 1, i);
            }
            goodSlot = lessOrEqKey + 1;
        }

        // 插入新条目
        markSlotUsed(goodSlot, true);
        Debug.log(1, "BTreeLeafPage.insertEntry: 新条目 tableId=%d pageId=%d slotId=%d", pid.getTableId(),
            pid.getPageNumber(), goodSlot);
        keys[goodSlot] = e.getKey();
        children[goodSlot] = e.getRightChild().getPageNumber();
        e.setRecordId(new RecordId(pid, goodSlot));
    }

    /**
     * 将一个条目从一个槽位移动到另一个槽位，并更新相应的头信息。
     */
    private void moveEntry(int from, int to) {
        if (!isSlotUsed(to) && isSlotUsed(from)) {
            markSlotUsed(to, true); // 标记目标槽位为已使用
            keys[to] = keys[from]; // 复制键
            children[to] = children[from]; // 复制子节点
            markSlotUsed(from, false); // 清除原槽位
        }
    }

    /**
     * 返回当前页面中实际存储的条目数（键的数量）
     */
    public int getNumEntries() {
        return numSlots - getNumEmptySlots() - 1;
    }

    /**
     * 返回当前页面中空闲槽位的数量
     */
    public int getNumEmptySlots() {
        int cnt = 0;
        // 从索引1开始计数，因为0号槽位未使用
        for (int i = 1; i < numSlots; i++)
            if (!isSlotUsed(i))
                cnt++;
        return cnt;
    }

    /**
     * 判断指定索引的槽位是否已被使用。
     *
     * 页面头部(header)使用一个字节数组表示每个槽位的状态：
     * 每个字节表示8个槽位的使用状态（1 表示已用，0 表示未用）。
     *
     * @param i 槽位索引
     * @return 如果该槽位被占用则返回 true，否则返回 false
     */
    public boolean isSlotUsed(int i) {
        int headerbit = i % 8; // 计算在字节中的位位置
        int headerbyte = (i - headerbit) / 8; // 计算属于哪个字节
        return (header[headerbyte] & (1 << headerbit)) != 0;
    }

    /**
     * 设置指定索引的槽位为已使用或未使用状态。
     *
     * @param i     槽位索引
     * @param value true 表示设置为已用，false 表示设为空闲
     */
    private void markSlotUsed(int i, boolean value) {
        int headerbit = i % 8;
        int headerbyte = (i - headerbit) / 8;

        Debug.log(1, "BTreeInternalPage.setSlot: setting slot %d to %b", i, value);
        if (value)
            header[headerbyte] |= 1 << headerbit; // 置1
        else
            header[headerbyte] &= (0xFF ^ (1 << headerbit)); // 置0
    }

    /**
     * 返回当前页面上所有有效条目的迭代器（不包括空槽位）。
     * 注意：调用 iterator.remove() 会抛出 UnsupportedOperationException。
     *
     * @return 条目迭代器
     */
    public Iterator<BTreeEntry> iterator() {
        return new BTreeInternalPageIterator(this);
    }

    /**
     * 返回当前页面上所有有效条目的逆序迭代器（不包括空槽位）。
     * 注意：调用 iterator.remove() 会抛出 UnsupportedOperationException。
     *
     * @return 逆序条目迭代器
     */
    public Iterator<BTreeEntry> reverseIterator() {
        return new BTreeInternalPageReverseIterator(this);
    }

    /**
     * 获取页面中第 i 个键值（保护方法，仅供迭代器使用）。
     *
     * @param i 键的索引
     * @return 第 i 个键值
     * @throws NoSuchElementException 如果索引无效或槽位未使用
     */
    protected Field getKey(int i) throws NoSuchElementException {

        // 第0个键未使用
        if (i <= 0 || i >= keys.length)
            throw new NoSuchElementException();

        try {
            if (!isSlotUsed(i)) {
                Debug.log(1, "BTreeInternalPage.getKey: slot %d in %d:%d is not used", i, pid.getTableId(),
                    pid.getPageNumber());
                return null;
            }

            Debug.log(1, "BTreeInternalPage.getKey: returning key %d", i);
            return keys[i];

        } catch (ArrayIndexOutOfBoundsException e) {
            throw new NoSuchElementException();
        }
    }

    /**
     * 获取页面中第 i 个子节点的页面ID（保护方法，仅供迭代器使用）。
     *
     * @param i 子节点索引
     * @return 子节点的页面ID
     * @throws NoSuchElementException 如果索引无效或槽位未使用
     */
    protected BTreePageId getChildId(int i) throws NoSuchElementException {

        if (i < 0 || i >= children.length)
            throw new NoSuchElementException();

        try {
            if (!isSlotUsed(i)) {
                Debug.log(1, "BTreeInternalPage.getChildId: slot %d in %d:%d is not used", i, pid.getTableId(),
                    pid.getPageNumber());
                return null;
            }

            Debug.log(1, "BTreeInternalPage.getChildId: returning child id %d", i);
            return new BTreePageId(pid.getTableId(), children[i], childCategory);

        } catch (ArrayIndexOutOfBoundsException e) {
            throw new NoSuchElementException();
        }
    }
}

/**
 * 实现 BTreeInternalPage 上条目的顺序迭代器。
 */
class BTreeInternalPageIterator implements Iterator<BTreeEntry> {
    int                     curEntry     = 1;
    BTreePageId             prevChildId  = null;
    BTreeEntry              nextToReturn = null;
    final BTreeInternalPage p;

    public BTreeInternalPageIterator(BTreeInternalPage p) {
        this.p = p;
    }

    public boolean hasNext() {
        if (nextToReturn != null)
            return true;

        try {
            if (prevChildId == null) {
                prevChildId = p.getChildId(0); // 获取第一个左子节点
                if (prevChildId == null) {
                    return false;
                }
            }

            while (true) {
                int entry = curEntry++;
                Field key = p.getKey(entry); // 获取键
                BTreePageId childId = p.getChildId(entry); // 获取右子节点

                if (key != null && childId != null) {
                    // 构造新的 BTreeEntry：左子节点是前一个，右子节点是当前 childId
                    nextToReturn = new BTreeEntry(key, prevChildId, childId);
                    nextToReturn.setRecordId(new RecordId(p.pid, entry));
                    prevChildId = childId;
                    return true;
                }
            }
        } catch (NoSuchElementException e) {
            return false;
        }
    }

    public BTreeEntry next() {
        if (hasNext()) {
            BTreeEntry toReturn = nextToReturn;
            nextToReturn = null;
            return toReturn;
        } else {
            throw new NoSuchElementException();
        }
    }

    public void remove() {
        throw new UnsupportedOperationException("remove not supported");
    }
}

/**
 * 实现了对 BTreeInternalPage 上条目的逆序迭代器。
 */
class BTreeInternalPageReverseIterator implements Iterator<BTreeEntry> {
    int                     curEntry;           // 当前条目索引
    BTreePageId             nextChildId  = null; // 下一个子节点ID
    BTreeEntry              nextToReturn = null; // 下一个待返回的条目
    final BTreeInternalPage p;                  // 关联的内部页面

    /**
     * 初始化逆序迭代器，从最大条目数开始，并找到第一个被使用的槽位。
     *
     * @param p 关联的 BTreeInternalPage 页面
     */
    public BTreeInternalPageReverseIterator(BTreeInternalPage p) {
        this.p = p;
        this.curEntry = p.getMaxEntries(); // 设置初始条目索引为最大条目数
        // 找到最后一个被使用的槽位
        while (!p.isSlotUsed(curEntry) && curEntry > 0) {
            --curEntry;
        }
    }

    /**
     * 判断是否还有下一个条目。
     *
     * @return 如果存在下一个条目则返回 true
     */
    public boolean hasNext() {
        if (nextToReturn != null)
            return true;

        try {
            if (nextChildId == null) {
                nextChildId = p.getChildId(curEntry);
                if (nextChildId == null) {
                    return false;
                }
            }
            while (true) {
                int entry = curEntry--;
                Field key = p.getKey(entry); // 获取键值
                BTreePageId childId = p.getChildId(entry - 1); // 获取左子节点ID
                if (key != null && childId != null) {
                    // 构造新的 BTreeEntry 条目
                    nextToReturn = new BTreeEntry(key, childId, nextChildId);
                    nextToReturn.setRecordId(new RecordId(p.pid, entry));
                    nextChildId = childId;
                    return true;
                }
            }
        } catch (NoSuchElementException e) {
            return false;
        }
    }

    public BTreeEntry next() {
        BTreeEntry next = nextToReturn;

        if (next == null) {
            if (hasNext()) {
                next = nextToReturn;
                nextToReturn = null;
                return next;
            } else
                throw new NoSuchElementException();
        } else {
            nextToReturn = null;
            return next;
        }
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }
}
